package com.fengye.algorithms.leecode;

/**
 * @Author fengye
 * @Date 2023/4/30 10:29
 **/
public class WordSearch79 {

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        // 找到首尾不同的字符
        int firstIdx = 0;
        int lastIdx = word.length() - 1;
        while (firstIdx < lastIdx && word.charAt(firstIdx) == word.charAt(lastIdx)) {
            firstIdx++;
            lastIdx--;
        }
        // 首尾不同的字符，查找其在数组中的数量。从小的开始会大大减少迭代次数
        if (firstIdx != lastIdx && word.charAt(firstIdx) != word.charAt(lastIdx)) {
            int firstCharCnt = 0;
            int lastCharCnt = 0;
            for (char[] bs : board) {
                for (char b : bs) {
                    if (b == word.charAt(firstIdx)) firstCharCnt++;
                    else if (b == word.charAt(lastIdx)) lastCharCnt++;
                }
            }
            if (lastCharCnt < firstCharCnt) {
                word = new StringBuilder(word).reverse().toString();
            }
        }

        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (check(i, j, board, visited,0, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(int i, int j, char[][] board,boolean[][] visited, int index, String word) {
        if (board[i][j] != word.charAt(index)) return false;
        if (index == word.length() - 1) return true;
        boolean flag = false;
        visited[i][j] = true;
        if (i - 1 >= 0 && !visited[i - 1][j]) {
            flag = check(i - 1, j, board, visited, index + 1, word);
        }
        if (!flag && i + 1 < board.length && !visited[i + 1][j]) {
            flag = check(i + 1, j, board, visited, index + 1, word);
        }
        if (!flag && j - 1 >= 0 && !visited[i][j - 1]) {
            flag = check(i, j - 1, board, visited, index + 1, word);
        }
        if (!flag && j + 1 < board[0].length && !visited[i][j + 1]) {
            flag = check(i, j + 1, board, visited, index + 1, word);
        }
        visited[i][j] = false;
        return flag;
    }

    public boolean exist1(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[row][col];
        for(int i=0;i<row;i++) {
            for(int j = 0; j < col;j++) {
                boolean flag = check(board, visited, word, i, j, 0);
                if(flag) {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, String word, int r, int c, int cur) {
        // 不相等的返回false
        if(board[r][c] != word.charAt(cur)) {
            return false;
        }
        // 到这里就是相等的
        // 找到最后一个
        if(cur == word.length() - 1) {
            return true;
        }
        // 已经访问过了
        visited[r][c] = true;
        // 4个方向
        int[][] dirs= {{1,0},{0,1},{-1,0},{0,-1}};
        boolean result = false;
        for(int[] dir : dirs) {
            int rn = r + dir[0];
            int cn = c + dir[1];
            if(rn >= 0 && rn < board.length && cn >= 0 && cn < board[0].length) {
                // 如果没有访问过
                if(!visited[rn][cn]) {
                    result = check(board, visited, word, rn, cn, cur + 1);
                    if(result) {
                        break;
                    }
                }
            }
        }
        // 回溯
        visited[r][c] = false;
        return result;
    }
}
